package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class VEAB3K {
    public static void main(String[] args) {
        Solution solution = new VEAB3K().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private boolean ok;  // 是否是二分图
        private boolean[] visited;
        private boolean[] color; // 染色情况

        // https://labuladong.gitee.io/algo/2/22/52/
        public boolean isBipartite(int[][] graph) {
            this.ok = true;
            this.visited = new boolean[graph.length];
            this.color = new boolean[graph.length];

            // 由于不是连通的
            for (int i = 0; i < graph.length; i++) {
                if (!visited[i]) {
                    dfs(graph, i);
                    // bfs(graph, i);
                }
            }

            // 有任意一个连通分量不符合，那整个图都不是二分图
            return ok;
        }

        // 0ms
        public void dfs(int[][] graph, int i) {
            // 不满足，无需再递归
            if (!ok) return;

            visited[i] = true;

            for (int v : graph[i]) {
                if (!visited[v]) {
                    // 下一个节点没有被访问过，下一个节点涂上相反的颜色
                    color[v] = !color[i];
                    dfs(graph, v);
                } else {
                    // 如果下一个节点被访问过，判断2者的颜色是否相等，相等就不满足二分图
                    if (color[v] == color[i]) {
                        ok = false;
                        return;
                    }
                }
            }
        }

        // 7ms
        public void bfs(int[][] graph, int i) {
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);

            while (!queue.isEmpty()) {
                if (!ok) return;
                Integer v = queue.poll();
                visited[v] = true;
                for (int m : graph[v]) {
                    if (!visited[m]) {
                        color[m] = !color[v];
                        queue.offer(m);
                    } else {
                        if (color[v] == color[m]) {
                            ok = false;
                            return;
                        }
                    }
                }
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
